10340. Все во всем

По заданным двум строкам определить, является ли последовательность символов первой строки подпоследовательностью второй.

Вход. Каждая строка содержит два слова, состоящих из символов английского алфавита и цифр. Слова разделены пробелом.

Выход. Для каждого теста вывести в отдельной строке слово ‘Yes’ или ‘No’ в зависимости от того, является ли первая строка подпоследовательностью второй.

Пример входа

sequence subsequence

person compression

VERDI vivaVittorioEmanueleReDiItalia

caseDoesMatter CaseDoesMatter

Пример выхода

Yes

No

Yes

No

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Задача решается жадным методом. Читаем первое слово a₀a₁…a_n-1 в символьный массив line. Второе слово читаем посимвольно. Установим i = 0. Если прочитан символ второго слова, равный a_i, то значение i увеличивается на 1. Если после прочтения второго слова i = n, то первое слово является подпоследовательностью второго.

Реализация алгоритма

Первое слово храним в массиве line.

char line[1000000];

Пока не конец файла, читаем входные тесты. Заносим первое слово в массив line и вычисляем его длину в переменной len.

while (!feof(stdin))

{

scanf("%s ",&line);

len = strlen(line); i = 0;

Читаем посимвольно второе слово и изменяем значение переменной i в соответствии с выше описанным алгоритмом.

while(scanf("%c",&c),c != '\n')

if (c == line[i]) i++;

scanf("\n");

В зависимости от конечного значения переменной i выводим результат.

if (i == len) printf("Yes\n");

else printf("No\n");

}